home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-ietf-rolc-nhrp-00.txt < prev    next >
Text File  |  1993-10-15  |  30KB  |  727 lines
  1.  
  2. Routing over Large Clouds Working Group                    Juha Heinanen
  3. INTERNET DRAFT                                         (Telecom Finland)
  4. Expires Apr 15, 1994                                     Ramesh Govindan
  5. <draft-ietf-rolc-nhrp-00.txt>                                 (Bellcore)
  6.                                                         October 15, 1993
  7.  
  8.  
  9.                 NBMA Next Hop Resolution Protocol (NHRP)
  10.  
  11.  
  12. Status of this Memo
  13.  
  14.    This document is an Internet Draft.  Internet Drafts are working
  15.    documents of the Internet Engineering Task Force (IETF), its Areas,
  16.    and its Working Groups.  Note that other groups may also distribute
  17.    working documents as Internet Drafts.
  18.  
  19.    Internet Drafts are draft documents valid for a maximum of six
  20.    months.  Internet Drafts may be updated, replaced, or obsoleted by
  21.    other documents at any time.  It is not appropriate to use Internet
  22.    Drafts as reference material or to cite them other than as a
  23.    ``working draft'' or ``work in progress.''  Please check the 1id-
  24.    abstracts.txt listing contained in the internet-drafts Shadow
  25.    Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net,
  26.    ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any
  27.    Internet Draft.
  28.  
  29. Abstract
  30.  
  31.    This document describes the NBMA Next Hop Resolution Protocol (NHRP).
  32.    NHRP can be used by a source terminal (host or router) connected to a
  33.    Non-Broadcast, Multi-Access link layer (NBMA) network to find out the
  34.    IP and NBMA addresses of the "NBMA next hop" towards a destination
  35.    terminal.  The NBMA next hop is the destination terminal itself, if
  36.    the destination is connected to the NBMA network.  Otherwise, it is
  37.    the egress router from the NBMA network that is "nearest" to the
  38.    destination terminal.  Although this document focuses on NHRP in the
  39.    context of IP, the technique is applicable to other network layer
  40.    protocols as well.
  41.  
  42. 1. Introduction
  43.  
  44.    The NBMA Next Hop Resolution Protocol (NHRP) allows a source terminal
  45.    (a host or router), wishing to communicate over a Non-Broadcast,
  46.    Multi-Access link layer (NBMA) network, to find out the IP and NBMA
  47.    addresses of the "NBMA next hop" towards a destination terminal.  The
  48.    NBMA next hop is the destination terminal itself, if the destination
  49.    is connected to the NBMA network.  Otherwise, it is the egress router
  50.  
  51.  
  52.  
  53. Heinanen & Govindan      Expires April 15, 1994                 [Page 1]
  54.  
  55. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  56.  
  57.  
  58.    (out of the NBMA network) nearest to the destination terminal.
  59.  
  60.    Conventional hop-by-hop IP routing may not be sufficient to resolve
  61.    the "NBMA next hop" towards the destination terminal.  An NBMA
  62.    network may, in general, consist of multiple logically independent IP
  63.    subnets (LISs, [3]); IP routing would only resolve the next hop LIS
  64.    towards the destination terminal.
  65.  
  66.    Once the NBMA next hop has been resolved, the source may either start
  67.    sending IP packets to the destination (in a connectionless NBMA
  68.    network such as SMDS) or may first establish a connection to the
  69.    destination with the desired bandwidth and QOS characteristics (in a
  70.    connection oriented NBMA network such as ATM).
  71.  
  72.    An NBMA network can be non-broadcast either because it technically
  73.    doesn't support broadcasting (e.g. an X.25 network) or because
  74.    broadcasting is not feasible for one reason or another (e.g. an SMDS
  75.    broadcast group or an extended Ethernet would be too large).
  76.  
  77. 2. Protocol Overview
  78.  
  79.    In this section, we briefly describe how a source S uses NHRP to
  80.    determine the "NBMA next hop" to destination D.  S first determines
  81.    the next hop to D through normal routing processes.  If this next hop
  82.    is reachable through its NBMA interface, S formulates an NHRP request
  83.    containing the source and destination IP addresses and QOS
  84.    information.  S then forwards the request to an entity called the
  85.    "Next Hop Server" (NHS).
  86.  
  87.    For administrative and policy reasons, a physical NBMA network may be
  88.    partitioned into several disjoint logical NBMA networks (discussed
  89.    later in this section); NHSs cooperatively resolve the NBMA next hop
  90.    within their logical NBMA network. Unless otherwise specified, we use
  91.    NBMA network to mean logical NBMA network.
  92.  
  93.    Each NHS "serves" a pre-configured set of terminals and peers with a
  94.    pre-configured set of NHSs, which all belong to the same NBMA
  95.    network.  An NHS exchanges routing information with its peers (and
  96.    possibly with the terminals it serves) using regular routing
  97.    protocols.  (However, an NHS, unless it is also an egress/ingress
  98.    router, need not necessarily be able to switch regular IP packets).
  99.    This exchange is used to construct a forwarding table per QOS in
  100.    every NHS.  The forwarding table determines the next hop NHS towards
  101.    the NHRP request's destination. This next hop NHS may depend on the
  102.    request's QOS information.
  103.  
  104.    After receiving an NHRP request, the NHS checks if it "serves" D.  If
  105.    so, the NHS resolves D's NBMA address, using mechanisms beyond the
  106.  
  107.  
  108.  
  109. Heinanen & Govindan      Expires April 15, 1994                 [Page 2]
  110.  
  111. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  112.  
  113.  
  114.    scope of this document (examples of such mechanisms include ARP [1,
  115.    2] and pre-configured tables).  The NHS then either forwards the NHRP
  116.    request to D or generates a positive NHRP reply on its behalf.  The
  117.    reply contains D's (D is S's NBMA next hop) IP and NBMA address and
  118.    is sent back to S.  NHRP replies usually traverse the same sequence
  119.    of NHSs as the NHRP request (in reverse order, of course).
  120.  
  121.    If the NHS does not serve D, it extracts from its forwarding table
  122.    the next hop towards D.  If no such next hop entry is found, the NHS
  123.    generates a negative NHRP reply.
  124.  
  125.    If the next hop is behind the NHS's NBMA interface, the NHS forwards
  126.    the NHRP request to the next hop.  If the next hop is behind some
  127.    other interface, the NHS may be willing to act as an egress router
  128.    for traffic bound to D.  In that case, the NHS generates a positive
  129.    NHRP reply containing its own IP and NBMA address (i.e., the NHS is
  130.    the NBMA next hop from S to D).
  131.  
  132.    An NHS receiving an NHRP reply may cache the NBMA next hop
  133.    information contained therein.  To a subsequent NHRP request, this
  134.    NHS might respond with the cached, non-authoritative, NBMA next hop
  135.    or with cached negative information. If a communication attempt based
  136.    on non-authoritative information fails, a source terminal can choose
  137.    to send an authoritative NHRP request.  NHSs never respond to
  138.    authoritative NHRP requests with cached information.
  139.  
  140.    NHRP requests and replies never cross the borders of a logical NBMA
  141.    network.  Thus, IP traffic out of and into a logical NBMA network
  142.    always traverses an IP router at its border.  Network layer filtering
  143.    can then be implemented at these border routers.
  144.  
  145.    NHRP provides a mechanism to aggregate NBMA next hop information in
  146.    NHS caches.  Suppose that NHS X is the NBMA next hop from S to D.
  147.    Suppose further that X is an egress router for all terminals sharing
  148.    an IP address prefix with D.  When X generates an NHRP reply in
  149.    response to a request, it may replace the IP address of D with this
  150.    prefix.  The prefix to egress router mapping in the reply is cached
  151.    in all NHSs on the path of the reply.  A subsequent (non-
  152.    authoritative) NHRP request for some destination that shares an IP
  153.    address prefix with D can be satisfied with this cached information.
  154.  
  155.    To dynamically detect link-layer filtering in NBMA networks, NHRP
  156.    incorporates a "Route record" in replies. This Route record contains
  157.    the network and link layer addresses of intermediate NHSs willing to
  158.    route packets from the source to the destination prefix. When a
  159.    source terminal is unable to open a connection to the responder, it
  160.    attempts to do so successively with one of the NHSs in the Route
  161.    record until it succeeds. This approach finds the optimal best hop in
  162.  
  163.  
  164.  
  165. Heinanen & Govindan      Expires April 15, 1994                 [Page 3]
  166.  
  167. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  168.  
  169.  
  170.    the presence of link-layer filtering.
  171.  
  172. 3. Configuration
  173.  
  174.    Terminals
  175.  
  176.      To participate in NHRP, a terminal connected to an NBMA network
  177.      should to be configured with the IP address(es) of its NHS(s).
  178.      These NHS(s) may be physically located on the terminal's default or
  179.      peer routers, so their addresses may be obtained from the
  180.      terminal's IP forwarding table.  If the terminal is attached to
  181.      several link layer networks (including logical NBMA networks), it
  182.      should also be configured to receive routing information from its
  183.      NHS(s) and peer routers so that the terminal can determine which IP
  184.      networks are reachable through which link layer networks.
  185.  
  186.    Next Hop Servers
  187.  
  188.      An NHS is configured with a set of IP address prefixes that
  189.      correspond to the IP addresses of the terminals it is serving.
  190.      Moreover, the NHS must be configured to exchange routing
  191.      information with its peer NHSs (if any).  If a served terminal is
  192.      attached to several link layer networks, the NHS may also need to
  193.      be configured to advertize routing information to such terminals.
  194.  
  195.      If an NHS is acting as an egress router for terminals connected to
  196.      other link layer networks than the NBMA network, the NHS must, in
  197.      addition to the above, be configured to exchange routing
  198.      information between the NBMA network and these other link layer
  199.      networks.
  200.  
  201.      In all cases, routing information is exchanged using regular
  202.      intra-domain and/or inter-domain routing protocols.
  203.  
  204. 4. Packet Formats
  205.  
  206.    NHRP requests and replies are carried as ICMP messages. This section
  207.    describes the packet formats of NHRP requests and replies:
  208.  
  209.    NHRP Request
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221. Heinanen & Govindan      Expires April 15, 1994                 [Page 4]
  222.  
  223. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  224.  
  225.  
  226.        0                   1                   2                   3
  227.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  228.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  229.       |     Type      |     Code      |          Checksum             |
  230.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  231.       |   Hop Count   |             Unused                            |
  232.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  233.       |                  Destination IP address                       |
  234.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  235.       |                    Source IP address                          |
  236.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  237.  
  238.    Type
  239.      19
  240.  
  241.    Code
  242.      A response to an NHRP request may contain cached information. If an
  243.      authoritative answer is desired, then code 2 (NHRP request for
  244.      authoritative information) should be used. Otherwise, a code value of 1
  245.      (NHRP request) should be used.
  246.  
  247.    Hop Count
  248.      The Hop count indicates the maximum number of NHSs that a request
  249.      or reply is allowed to traverse before being discarded.
  250.  
  251.    Source and Destination IP Addresses
  252.      Respectively, these are the IP addresses of the NHRP request
  253.      initiator and the terminal for which the NBMA next hop is desired.
  254.  
  255.    NHRP Reply
  256.  
  257.        0                   1                   2                   3
  258.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  259.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  260.       |     Type      |     Code      |          Checksum             |
  261.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  262.       |   Hop Count   |    Unused     |      Route record length      |
  263.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  264.       |                    Source IP address                          |
  265.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  266.       |                    Destination IP address                     |
  267.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  268.       |                    Destination mask                           |
  269.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  270.       |                                                               |
  271.       |                NHRP route record (variable)                   |
  272.       |                                                               |
  273.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  274.  
  275.  
  276.  
  277. Heinanen & Govindan      Expires April 15, 1994                 [Page 5]
  278.  
  279. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  280.  
  281.  
  282.    Type
  283.      20
  284.  
  285.    Code
  286.      NHRP replies may be positive or negative. An NHRP positive,
  287.      non-authoritative reply carries a code of 1, while a positive,
  288.      authoritative reply carries a code of 2. An NHRP negative,
  289.      non-authoritative reply carries a code of 3 and a negative,
  290.      authoritative reply carries a code of 4.  An NHS is not allowed to
  291.      reply to an NHRP request for authoritative information with cached
  292.      information, but may do so for an NHRP Request.
  293.  
  294.    Route Record Length
  295.      The length in words of the NHRP route record (see below).
  296.  
  297.    Source IP Address
  298.      The address of the initiator of the corresponding NHRP request.
  299.  
  300.    Destination IP Address and Mask
  301.      If the NHRP Request's destination is on the NBMA, the reply contains
  302.      that destination address and a mask of all 1s.  Otherwise, the
  303.      responder may choose to act as the egress router for all terminals in
  304.      the destination's subnet.  If so, the reply contains a prefix of the
  305.      requested destination IP address and the corresponding mask.
  306.  
  307.    NHRP Route Record
  308.      The NHRP route record is a list of NHRP "Route elements" for NHSs on
  309.      the path of a positive NHRP reply.  Only NHSs that are willing to act
  310.      as egress routers for packets from the source to the destination insert
  311.      a Route element in the NHRP reply.  Negative replies do not carry
  312.      Route elements.
  313.  
  314.      The first Route element is always that of the destination terminal or,
  315.      if the destination is not directly attached to the NBMA, that of the
  316.      responding egress router.  Each Route element is formatted as follows:
  317.  
  318.          0                   1                   2                   3
  319.          0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  320.         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  321.         |                    IP address                                 |
  322.         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  323.         | LL length       |           Link Layer (LL) address           |
  324.         +-+-+-+-+-+-+-+-+-+                                             |
  325.         |                  (variable length)                            |
  326.         +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  327.  
  328.      The LL length field is the length of the link layer address in
  329.      bits.  The LL address itself is zero-filled to the nearest 32-bit
  330.  
  331.  
  332.  
  333. Heinanen & Govindan      Expires April 15, 1994                 [Page 6]
  334.  
  335. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  336.  
  337.  
  338.      boundary.
  339.  
  340.      On the reply path, an NHS willing to route packets from source to
  341.      the destination prefix should append its Route element to the
  342.      current Route Record, adjust the Route record length appropriately,
  343.      and recompute the ICMP checksum.  The Route record is used to
  344.      discover link layer filters, as described in Section 2.
  345.  
  346.      If the first Route element's IP address and the destination's IP
  347.      address differ, the source terminal may assume that the reply was
  348.      generated by an egress router.
  349.  
  350.      An NHS may cache replies containing a Route record.  Subsequently,
  351.      when it responds to an NHRP request with the cached reply,
  352.      intermediate NHSs on the path to the initiator may attach Route
  353.      elements to the reply.
  354.  
  355. 5. Protocol Operation
  356.  
  357.    The external behavior of an NHS may be described in terms of two
  358.    procedures (processRequest and processReply) operating on two tables
  359.    (forwardingTable and cacheTable).  In an actual implementation, the
  360.    code and data structures may be realized differently.
  361.  
  362.    Each NHS has for each supported QOS an NHRP forwardingTable
  363.    consisting of entries with the fields:
  364.  
  365.        <networkLayerAddrPrefix, type, outIf, outIfAddr>
  366.  
  367.    In case the NHS is also a host or serving as a router, the NHRP
  368.    forwarding table may be integrated with the normal IP forwarding
  369.    table of the NHS.
  370.  
  371.    The networkLayerAddrPrefix field identifies a set of network layer
  372.    addresses known to the NHS.  It consists of two subfields <ipAddr,
  373.    mask>.
  374.  
  375.    The type field indicates the type of the networkLayerAddrPrefix.  The
  376.    possible values are:
  377.  
  378.    - locallyServed: The NHS is itself serving the
  379.      networkLayerAddrPrefix.  The outIf field denotes the NBMA interface
  380.      via which the served terminals can be reached and the outIfAddr
  381.      field has no meaning.  Such a forwardingTable entry has been
  382.      created by manual configuration.
  383.  
  384.    - nhsLearned: The NHS has learned about the networkLayerAddrPrefix
  385.      from another NHS.  The outIf and outIfAddr fields, respectively,
  386.  
  387.  
  388.  
  389. Heinanen & Govindan      Expires April 15, 1994                 [Page 7]
  390.  
  391. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  392.  
  393.  
  394.      denote the NBMA interface and IP address of this next hop NHS.
  395.      Such a forwardingTable entry is a result of network layer address
  396.      prefix information exchange with one of the NHS's peers.
  397.  
  398.    - externallyLearned: The NHS has learned about the
  399.      networkLayerAddrPrefix via normal IP routing from outside of the
  400.      NBMA network.  In this case, the NHS may act as an egress router
  401.      for the terminals sharing the networkLayerAddrPrefix. The outIf and
  402.      outIfAddr fields, respectively, denote the interface and IP address
  403.      of the next hop router.  If the outIfAddr field is empty, the
  404.      networkLayerAddrPrefix is assumed to be directly connected to the
  405.      outIf of the NHS.
  406.  
  407.    The protocol used to exchange networkLayerAddrPrefix information
  408.    among the NHSs or between NHSs and their peer routers can be any
  409.    regular IP intra-domain or inter-domain routing protocol.
  410.  
  411.    In addition to the forwardingTable, each NHS has for each supported
  412.    QOS an NHRP cacheTable consisting of entries with the fields:
  413.  
  414.        <networkLayerAddrPrefix, routeElementList>
  415.  
  416.    The entries in the cacheTable are learned from NHRP replies
  417.    traversing the NHS. The networkLayerAddrPrefix field identifies a set
  418.    of IP addresses sharing a common Route record.  The
  419.    networkLayerAddrPrefix field consists of two subfields <ipAddr,
  420.    mask>.  The routeElementList field is either empty (in case of a
  421.    negative cache entry) or consists of a list of subfields of the form
  422.    <ipAddr, nbmaAddr>.
  423.  
  424.    The cacheTable entries could also include a timeStamp field to be
  425.    used to age cacheTable entries after a certain hold period.
  426.  
  427.    The following pseudocode defines how NBMA NHRP requests and replies
  428.    are processed by an NHS.
  429.  
  430.  
  431.  
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442.  
  443.  
  444.  
  445. Heinanen & Govindan      Expires April 15, 1994                 [Page 8]
  446.  
  447. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  448.  
  449.  
  450.      procedure processRequest(request);
  451.        let bestMatch == matchForwardingTable(request.dIPa) do
  452.           if bestMatch then
  453.              if bestMatch.type == locallyServed then
  454.                 let nbmaAddr == arp(request.dIPa) do
  455.                    if nbmaAddr then
  456.                       genPosAuthReply(request.sIPa,
  457.                          request.dIPa, 0xFFFFFFFF,
  458.                          request.dIPa, nbmaAddr)
  459.                    else
  460.                       genNegAuthReply(request.sIPa, request.dIPa)
  461.                    end
  462.                 end
  463.              elseif bestMatch.type == nhsLearned then
  464.                 if not requestForAuthInfo?(request) then
  465.                    let cacheMatch == matchCacheTable(request.dIPa) do
  466.                       if cacheMatch then
  467.                          if cacheMatch.routeElementList == EMPTY then
  468.                             genNegNonAuthReply(request.sIPa, request.dIPa)
  469.                          else
  470.                             genPosNonAuthReply(request.sIPa,
  471.                                cacheMatch.networkLayerAddrPrefix.ipAddr,
  472.                                cacheMatch.networkLayerAddrPrefix.mask,
  473.                                cacheMatch.routeElementList);
  474.                          end
  475.                       else /* no cache match */
  476.                          forwardRequest(request, bestMatch.OutIf,
  477.                             bestMatch.OutIfAddr)
  478.                       end
  479.                    end
  480.                 else /* request for authoritative information */
  481.                    forwardRequest(request, bestMatch.OutIf,
  482.                       bestMatch.OutIfAddr)
  483.                 end
  484.              else  /* bestMatch.type == externallyLearned */
  485.                 genPosAuthReply(request.sIPa,
  486.                    bestMatch.networkLayerAddrPrefix.ipAddr,
  487.                    bestMatch.networkLayerAddrPrefix.mask,
  488.                    selfIpAddr, selfNbmaAddr)
  489.              end
  490.           else /* no match in forwardingTable */
  491.              genNegAuthReply(request.sIPa, request.dIPa)
  492.           end
  493.        end
  494.      end
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501. Heinanen & Govindan      Expires April 15, 1994                 [Page 9]
  502.  
  503. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  504.  
  505.  
  506.      procedure processReply(reply);
  507.        addCacheTableEntry(reply.dIPa, reply.dm, reply.routeRecord);
  508.        if reply.sIPa == selfIpAddr then
  509.           /* reply is to the NHS itself */
  510.        else
  511.           let bestMatch == matchForwardingTable(reply.sIPa) do
  512.              if bestMatch then
  513.                 if bestMatch.type != externallyLearned then
  514.                    forwardReply(reply, bestMatch.outIf, bestMatch.outIfAddr)
  515.                 else /* bestMatch.type == externallyLearned */
  516.                    /* request should never originate outside of the NBMA */
  517.                 end
  518.              end
  519.           end
  520.        end
  521.      end
  522.  
  523.    The semantics of the procedures and constants used in the pseudocode
  524.    are explained below.
  525.  
  526.    matchForwardingTable(ipAddress) returns the forwardingTable entry
  527.    whose networkLayerAddrPrefix field is the longest match for ipAddress
  528.    or FALSE if no match is found.
  529.  
  530.    arp(ipAddress) resolves the NBMA address corresponding to ipAddress.
  531.    It returns FALSE if the resolution fails.
  532.  
  533.    genPosAuthReply(sourceIpAddr, destinationIpAddr, destinationMask,
  534.    originatorIpAddr, originatorNbmaAddr) generates a positive,
  535.    authoritative reply with sourceIpAddr, destinationIpAddr, and
  536.    destinationMask in Source IP address, Destination IP address and
  537.    Destination mask fields, respectively.  The Route record field of the
  538.    reply consists of one Route element that contains originatorIpAddr
  539.    and originatorNbmaAddr as its IP and Link layer addresses.
  540.  
  541.    genNegAuthReply(sourceIpAddr, destinationIpAddr) and
  542.    genNegNonAuthReply(sourceIpAddr, destinationIpAddr) respectively
  543.    generate a negative, authoritative and non-authoritative reply with
  544.    sourceIpAddr and destinationIpAddr in Source IP address and
  545.    Destination IP address fields.  The Destination mask field has always
  546.    value 0xFFFFFFFF and the route Record field is empty.
  547.  
  548.    selfIpAddr and selfNbmaAddr denote the egress router's own IP and
  549.    NBMA addresses in the NBMA via which its peer NHSs can be reached.
  550.  
  551.    requestForAuthInfo?(request) tests if request is a Request for
  552.    authoritative information.
  553.  
  554.  
  555.  
  556.  
  557. Heinanen & Govindan      Expires April 15, 1994                [Page 10]
  558.  
  559. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  560.  
  561.  
  562.    matchCacheTable(ipAddr) returns a cacheTable entry whose
  563.    networkLayerAddr field is the best match for ipAddr or FALSE if no
  564.    match is found.
  565.  
  566.    genPosNonAuthReply(sourceIpAddr, destinationIpAddr, destinationMask,
  567.    routeElementList) generates a positive, non-authoritative reply with
  568.    sourceIpAddr, destinationIpAddr, and destinationMask in Source IP
  569.    address, Destination IP address and Destination mask fields,
  570.    respectively.  The Route record field of the reply is constructed
  571.    from routeElementList.
  572.  
  573.    forwardRequest(request, interface, ipAddr) decrements the Hop count
  574.    field of request, recomputes the ICMP Checksum field, and forwards
  575.    request to ipAddr of interface provided that the value of the Hop
  576.    count field remains positive.
  577.  
  578.    addCacheTableEntry(ipAddr, mask, routeRecord) adds a new entry to the
  579.    cacheTable or overwrites an existing entry whose
  580.    networkLayerAddrPrefix field is equal to <ipAddr, mask>.  A new entry
  581.    is not added if matchCacheTable(ipAddr) returns an entry whose
  582.    routeElementList is equivalent to routeRecord.  The
  583.    networkLayerAddrPrefix field of the new entry is <ipAddr, mask>.  The
  584.    routeElementList field is constructed from routeRecord.  In addition,
  585.    if the NHS processing the reply would be willing to serve as an
  586.    egress router for <ipAddr, mask>, it should add a new Route element
  587.    <selfIpAddr, selfNbmaAddr> to the end of the routeElementList field.
  588.  
  589.    forwardReply(reply, interface, ipAddr) decrements the Hop count field
  590.    of request, recomputes the ICMP Checksum field, and forwards request
  591.    to ipAddr of interface provided that the value of the Hop count field
  592.    remains positive.  If the NHS processing the reply would be willing
  593.    to serve as an egress router for <reply.dIPa, reply.mask>, it should,
  594.    before recomputing the Checksum field, add a new Route element
  595.    <selfIpAddr, selfNbmaAddr> to the end of reply.routeRecord.
  596.  
  597.  
  598.    An NBMA terminal has, for each supported QOS, a forwardingTable and
  599.    one or more cacheTables.  The former can be the terminal's IP
  600.    forwarding table and is either manually configured or filled via
  601.    routing information exchange with the terminal's NHSs or peer
  602.    routers.  There is one cacheTable per connected NBMA network.  If the
  603.    terminal's forwardingTable shows that a particular destination is
  604.    behind an NBMA network, the terminal first consults the corresponding
  605.    cacheTable.  If no match is found, it generates an NHRP request to
  606.    the NHS pointed to by the forwardingTable entry.  When the reply
  607.    arrives, the terminal updates the appropriate cacheTable in the same
  608.    way as an NHS does.
  609.  
  610.  
  611.  
  612.  
  613. Heinanen & Govindan      Expires April 15, 1994                [Page 11]
  614.  
  615. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  616.  
  617.  
  618. 6. Discussion
  619.  
  620.    The result of an NHRP request depends on how routing is configured
  621.    among the NHSs of an NBMA network.  If the destination terminal is
  622.    directly connected to the NBMA network and the NHSs always prefer
  623.    NBMA routes over routes via other link layer networks, the NHRP
  624.    replies always return the NBMA address of the destination terminal
  625.    itself rather than the NBMA address of some egress router.  For
  626.    destinations outside the NBMA network, egress routers and routers in
  627.    the other link layer networks should exchange routing information so
  628.    that the optimal egress router is always found.
  629.  
  630.    When the NBMA next hop towards a destination is not the destination
  631.    terminal itself, the optimal NBMA next hop may change dynamically.
  632.    This can happen, for instance, when an egress router nearer to the
  633.    destination becomes available.  To detect this change, a source
  634.    terminal can periodically reissue the NHRP request.  Alternatively,
  635.    the source can be configured to receive routing information from its
  636.    NHSs.  When it detects an improvement in the route to the
  637.    destination, the source can reissue the NHRP request to obtain the
  638.    current optimal NBMA next hop.
  639.  
  640.    In addition to NHSs, an NBMA terminal could also be associated with
  641.    one or more regular routers that could act as "connectionless
  642.    servers" for the terminal.  Then the terminal could choose to resolve
  643.    the NBMA next hop or just send the IP packets to one of the
  644.    terminal's connectionless servers.  The latter option may be
  645.    desirable if communication with the destination is short-lived and/or
  646.    doesn't require much network resources.  The connectionless servers
  647.    could, of course, be physically integrated in the NHSs by augmenting
  648.    them with IP switching functionality.
  649.  
  650.    NHRP supports portability of NBMA terminals.  A terminal can be moved
  651.    anywhere within the NBMA network and still keep its original IP
  652.    address as long as its NHS(s) remain the same.  Requests for
  653.    authoritative information will always return the correct link layer
  654.    address.
  655.  
  656. References
  657.  
  658.    [1] Address Resolution Protocol, David C. Plummer, RFC 826.
  659.  
  660.    [2] Classical IP and ARP over ATM, Mark Laubach, Internet Draft.
  661.  
  662.    [3] Transmission of IP datagrams over the SMDS service, J. Lawrence
  663.    and
  664.          D. Piscitello, RFC 1209.
  665.  
  666.  
  667.  
  668.  
  669. Heinanen & Govindan      Expires April 15, 1994                [Page 12]
  670.  
  671. INTERNET DRAFT                 NBMA NHRP                October 15, 1993
  672.  
  673.  
  674. Acknowledgements
  675.  
  676.    We would like to thank John Burnett of Adaptive, Dennis Ferguson of
  677.    ANS, Joel Halpern of Network Systems, and Paul Francis of Bellcore
  678.    for their valuable insight and comments to earlier versions of this
  679.    draft.
  680.  
  681. Authors' Addresses
  682.  
  683.    Juha Heinanen                           Ramesh Govindan
  684.    Telecom Finland,                        Bell Communications Research
  685.    PO Box 228,                             MRE 2P-341, 445 South Street
  686.    SF-33101 Tampere,                       Morristown, NJ 07960
  687.    Finland
  688.  
  689.    Phone: +358 49 500 958                  Phone: +1 201 829 4406
  690.    Email: Juha.Heinanen@datanet.tele.fi    Email: rxg@thumper.bellcore.com
  691.  
  692.  
  693.  
  694.  
  695.  
  696.  
  697.  
  698.  
  699.  
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708.  
  709.  
  710.  
  711.  
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724.  
  725. Heinanen & Govindan      Expires April 15, 1994                [Page 13]
  726.  
  727.